JZ17 树的子结构

https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

这题确实挺难的，不过把问题化成一个个子问题就不难了

1. 先找到子结构的根
2. 找到根后比对子结构是否相同
3. 可能存在节点的值是一样的情况，所以需要重新找，因此得重复上面两个步骤

import java.util.*;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    // 这里负责找到根
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
       if (root1 == null || root2 == null) return false;

       boolean result = false;
       // 如果找到了根，就执行遍历，判断是否相同
       if (root1.val == root2.val) {
           // 因为可能节点一样，但是并不是子结构的情况，所以可能需要重新找
           result = tree1HaveTree2(root1, root2);
       }
        
       if (! result) result = HasSubtree(root1.left, root2); // 如果不是子节点则重新找左边
       if (! result) result = HasSubtree(root1.right, root2); // 还不是就找右边
        
        return result;
    }
    
    // 找到根后遍历是否相同
    public boolean tree1HaveTree2(TreeNode root1,TreeNode root2 ) {
        if (root2 == null) return true; // 因为子结构可能只占一部分，所以为空时则说明当前子结构遍历完了
        
        if (root1 == null) return false;
        
        if (root2.val != root1.val) return false; // 如果有一个不同就遍历失败
        
        return tree1HaveTree2(root1.left, root2.left) && 
            tree1HaveTree2(root1.right, root2.right);
    }
}